from .list_dict import ListDict


def width_first(source_states, children_func, cost_func=None, target_func=None):
    """
    width_first searching algorithm
    :param source_states: list or tuple or set of the source {State}s of the searching.
    A {State} is an object that contains the attributes of a state, such as the (x, y)
    of a point in a 2-D area which is used to search the shortest path from a point to
    another one. A state object MUST override its __hash__() and __eq__() methods
    because this method uses dict and set to store states.
    :param children_func: a function used to get children of a state, and which contains
    only one parameter 'state' representing the current state.
    :param cost_func: a function which returns the cost of a state and which contains 2
    parameters 'parent' and 'child' while the 'parent' is the parent state and the 'child'
    is the state. None means the function returns constant 1 for any input.
    :param target_func: a function with only one parameter which returns True if the parameter
    is a target state. None means that the searching has no specified targets,
    and the algorithm stops only if there is no more new state found.
    :return: a dict, which key is a target {State} and the corresponding value
    is a tuple of (path, cost) where the path is a list of {State}s representing the
     shortest path
    from the nearest source state to the target, and the cost is the sum of the costs of all the
    states, excluding the source state, in the path. Please note: path[0] is a source state,
    path[-1] is the target state. If the target_states is None, the dict contains all
    states that can be visited from any one of the sources.
    """
    if cost_func is None:
        cost_func = lambda parent, child: 1
    open = ListDict()  # open表，用来存放当前的叶子结点
    for state in source_states:
        open.append(state, (None, 0.))

    if target_func is None:
        target_func = lambda state: False
    close = {}
    while len(open) > 0:
        current, (parent, cost) = open.pop(0)
        close[current] = (parent, cost)
        if not target_func(current):
            for child in children_func(current):
                if child in close:
                    continue
                new_cost = cost + cost_func(current, child)
                if child in open:
                    _, old_cost = open[child]
                    if old_cost > new_cost:
                        del open[child]
                    else:
                        continue

                def _compare(_, v):
                    _, cost = v
                    return cost - new_cost
                open.insert_by_order(child, _compare, (current, new_cost))
    return {state: _get_path_cost(state, close) for state in close}


def _get_path_cost(state, close):
    result = [state]
    parent, cost = close[state]
    while parent is not None:
        result.insert(0, parent)
        parent, _ = close[parent]
    return result, cost